package com.sakura.二分答案;

public class Code1011_在D天内送达包裹的能力 {

    public static void main(String[] args) {
        int[] weights = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(new Code1011_在D天内送达包裹的能力().shipWithinDays(weights, 1));
    }

    public int shipWithinDays(int[] weights, int days) {
        int maxWeight = 0;
        int sumWeight = 0;
        for (int weight : weights) {
            maxWeight = Math.max(maxWeight, weight);
            sumWeight += weight;
        }

        int left = maxWeight - 1;
        int right = sumWeight;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(weights, mid, days)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    public boolean check(int[] weights, int mid, int days) {
        int sum = 0;
        int day = 1;
        for (int weight : weights) {
            sum += weight;
            if (sum > mid) {
                day++;
                sum = weight;
            }
        }
        return day <= days;
    }
}
